package _11_整理题目._9_高频题目;

import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 一、暴力双重 for 循环，第二层循环中需要判断之前的 数组中是否包含 num[i]
 * 
 * 二、优化，使用 HashMap 降低判断 数组中是否包含 num[i] 需要 O(1) 事件复杂度
 * 
 * 三、发现 二 中 其实是用双指针在 hashmap 中维护了一个队列，可以直接使用队列来处理
 *      但是队列中判断 数组中是否包含 num[i] 的时间复杂度为O(n)
 * 
 */
public class _04_最长无重复子数组 {
    
    public int maxLengthHashMap (int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        int start = 0;
        int max = 1;
        for (int j = 0; j < arr.length; j++) {
            if (map.containsKey(arr[j])) {
                start = Math.max(start, map.get(arr[j])+1);
            }
            map.put(arr[j], j);
            max = Math.max(max, j-start+1);
        }
        return max;
    }
    
    public int maxLengthQueue (int[] arr) {
        Queue<Integer> queue = new LinkedList<>();
        int max = 0;
        for (int num : arr) {
            while (queue.contains(num)) {
                queue.poll();
            }
            queue.offer(num);
            max = Math.max(max, queue.size());
        }
        return max;
    }
    
    @Test
    public void test() {
        int[] input = {2, 3, 4, 5, 3};
        System.out.println(maxLengthHashMap(input));
        System.out.println(maxLengthQueue(input));
    }
    
}
